package com.itheima.leetcode.od.b.dynamicprogramming;

/**
 * (C卷,100分)- 判断字符串子序列（Java & JS & Python）
 * <p>
 * 字符串子序列II
 * <p>
 * 题目描述
 * <p>
 * 给定字符串 target和 source，判断 target是否为 source 的子序列。
 * <p>
 * 你可以认为target和 source 中仅包含英文小写字母。
 * <p>
 * 字符串 source 可能会很长（长度~=500,000），而 target是个短字符串（长度<=100)。
 * <p>
 * 字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。
 * <p>
 * （例如，”abc”是”aebycd”的一个子序列，而”ayb”不是）。
 * <p>
 * 请找出最后一个子序列的起始位置。
 * <p>
 * 输入描述
 * <p>
 * 第一行为target，短字符串（长度 <=100）
 * 第二行为source，长字符串（长度 ~= 500,000）
 * <p>
 * 输出描述
 * <p>
 * 最后一个子序列的起始位置，即最后一个子序列首字母的下标
 * <p>
 * 备注
 * 若在source中找不到target，则输出-1。
 * <p>
 * 用例
 * <p>
 * 输入	abc
 * abcaybec
 * 输出	3
 * 说明	这里有两个abc的子序列满足，取下标较大的，故返回3。
 * <p>
 * 题目解析
 * <p>
 * 此题是华为机试 - 字符串序列判定_伏城之外的博客-CSDN博客
 * 的进阶题。
 */
public class LastLCSubsequence {
    public static void main(String[] args) {
        /*Scanner sc = new Scanner(System.in);*/

        System.out.println(getResult("abc", "abcaybec"));
    }

    /**
     * 双指针
     *
     * @param target
     * @param source
     * @return
     */
    public static int getResult(String target, String source) {
        int cursor = target.length() - 1;
        for (int i = source.length() - 1; i >= 0; i--) {
            if (source.charAt(i) == target.charAt(cursor)) {
                cursor--;
                if (cursor < 0) {
                    return i;
                }
            }
        }
        return -1;
    }
}
